package com.aqie.medium.greedy;

import java.util.*;

/**
 * 621 任务调度器
 * 1. TreeMap只能根据key来排序，是不能根据value来排序的
 * 2,
 */
public class LeastInterval {
    /**
     * (A-1)*n + A-1 + (与A出现相同次数的任务,包括A)
     * @param n
     * @return
     */
    public static int leastInterval(char[] tasks, int n) {
        Map<Character, Integer> map = new HashMap<>();
        for (char task : tasks) {
            map.put(task, map.getOrDefault(task, 0) + 1);
        }

        List<Integer> nums = new ArrayList<>();
        // 遍历 map, 到 List
        for (Map.Entry<Character, Integer> entry : map.entrySet()){
            System.out.println(entry.getKey() + " " + entry.getValue());
            nums.add(entry.getValue());
        }
        Collections.sort(nums, (o1, o2) -> o2 - o1);


        int count = 0;
        int A = nums.get(0);
        for (Integer num : nums) {
            if (!num.equals(A)) break;
            count++;
        }
        int res = (A-1) * (n + 1) + count;

        return res > tasks.length ? res :tasks.length;
    }

    // 数组优化
    public int leastInterval2(char[] tasks, int n) {
        if(tasks.length==0) return 0;
        int ch[] = new int[256];
        // <!-- 统计字母出现的频率 -->
        for(char c : tasks){
            ch[c]++;
        }
        // <!-- 获取出现最多的次数 -->
        int max = Integer.MIN_VALUE;
        for(int i :ch){
            max =Math.max(max,i);
        }
        // <!-- 得到一共有几个字母都以最高频次出现 -->
        int  count=0;
        for(int i :ch){
            if(i==max) ++count;
        }
        return Math.max((n+1)*(max-1)+count,tasks.length);
    }



    public static void main(String[] args) {
        char[] tasks = {'A','A','A','B','B','B','C','D','D'};
        // 根据 key 降序排列
        Map<Character, Integer> map = new TreeMap<>((o1, o2) -> o2 - o1);
        for (char task : tasks) {
            map.put(task, map.getOrDefault(task, 0) + 1);
        }

        List<Integer> nums = new ArrayList<>();
        // 遍历 map, 到 List
        for (Map.Entry<Character, Integer> entry : map.entrySet()){
            System.out.println(entry.getKey() + " " + entry.getValue());
            nums.add(entry.getValue());
        }

        // 根据 value 升序排列
        List<Map.Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
        list.sort(Comparator.comparing(Map.Entry::getValue));
        // {D=2, C=1, B=3, A=3}
        System.out.println(map);
        // [C=1, D=2, B=3, A=3]
        System.out.println(list);

        // list 排序
        Collections.sort(nums, (o1, o2) -> o2 - o1);
        // [1, 2, 3, 3]
        System.out.println(nums);

        int count = 0;
        for (int i = 0; i < nums.size(); i++){
            if (!nums.get(i).equals(nums.get(0))) break;
            count++;
        }
        System.out.println(count);
        leastInterval(tasks,1);
    }
}
